// --------------------------------------
    // 排序算法
        //对常见的排序算法实现
        //插入、冒泡、选择、希尔、归并、堆、快速、
// --------------------------------------


#ifndef __SORT_ALOGR__
#define __SORT_ALOFR__

#include <iostream>
#include <vector>
#include <utility>

namespace ymbxUtil{
    //插入排序
        //原理：向n-1个有序元素中插入第n个元素确保有序
        //时间复杂度：最坏——O(N*N) 最好——O(N)
    void InsertSort(std::vector<int>& arr){
        int n=arr.size();
        for(int i=1;i<n;++i){
            int key=arr[i];
            int j;
            for(j=i-1;j>=0;--j){
                if(key>=arr[j]){
                    break;
                }
                arr[j+1]=arr[j];
            }
            arr[j+1]=key;
        }
    }

    //选择排序
        //原理：每次遍历选择最小值元素放在最开头
        //时间复杂度：O(N*N)
    void SelectSort(std::vector<int>& arr){
        int n=arr.size();
        for(int i=0;i<n;++i){
            for(int j=i+1;j<n;++j){
                if(arr[i]>arr[j]){
                    std::swap(arr[i],arr[j]);
                }
            }
        }
    }

    //冒泡排序
        //原理：每次遍历比较两个相邻的元素确定他们的位置
        //时间复杂度：最好O(N) 最坏O(N*N)  平均O(N*N) 
    void BubbleSort(std::vector<int>& arr){
        int n=arr.size();
        for(int i=0;i<n-1;++i){
            int flag=true;
            for(int j=0;j<n-1-i;++j){
                if(arr[j]>arr[j+1]){
                    std::swap(arr[j],arr[j+1]);
                    flag=false;
                }
            }
            if(flag){
                break;
            }
        }
    }

    //希尔排序
        //原理：设置一个增量，将待排序数组分割为若干个子数组分别进行插入排序，然后逐步缩小增量直至为1，完成排序
        //时间复杂度：最坏：O(N*N) 最好O(N*logN) 平均O(N*logN)
    void ShellSort(std::vector<int>& arr){
        int n=arr.size();
        int gap=n/2;
        while(gap>0){
            for(int i=gap;i<n;++i){
                int key=arr[i];
                int j;
                for(j=i-gap;j>=0;j-=gap){
                    if(key>=arr[j]){
                        break;
                    }
                    arr[j+gap]=arr[j];
                }
                arr[j+gap]=key;
            }
            gap/=2;
        }
    }

    //归并排序
        //原理：采用分治法的思想通过不断的分解、合并将数组排序。有递归和迭代两种实现方法
        //时间复杂度：O(N*logN)
        //空间复杂度：O(N)
    void DivideConquer(std::vector<int>& arr1,std::vector<int>& arr2,int start,int end){
        if(start>=end){
            return;
        }
        int mid=(end-start)/2+start;
        int s1=start,e1=mid;
        int s2=mid+1,e2=end;
        DivideConquer(arr1,arr2,s1,e1);
        DivideConquer(arr1,arr2,s2,e2);
        int k=start;
        while(s1<=e1 && s2<=e2){
            arr2[k++]=arr1[s1]>arr1[s2]?arr1[s2++]:arr1[s1++];
        }
        while(s1<=e1){
            arr2[k++]=arr1[s1++];
        }
        while(s2<=e2){
            arr2[k++]=arr1[s2++];
        }
        for(start;start<=end;++start){
            arr1[start]=arr2[start];
        }
    }
    void MergeSort(std::vector<int>& arr){
        int n=arr.size();
        std::vector<int> arr2(n,0);
        DivideConquer(arr,arr2,0,n-1);
    }

    //快速排序
        //原理：基于分治思想，设置一个基准值将待排序数组分为两部分然后递归进行排序
        //时间复杂度：O(N*logN)
    int Parition(std::vector<int>& arr,int low,int high){
        int pivot=arr[low];
        while(low<high){
            while(low<high && pivot<=arr[high]){
                --high;
            }
            arr[low]=arr[high];
            while(low<high && pivot>=arr[low]){
                ++low;
            }
            arr[high]=arr[low];
        }
        arr[low]=pivot;
        return low;
    }
    void _QuickSort(std::vector<int>& arr,int low,int high){
        if(low<high){
        int pivot=Parition(arr,low,high);
        _QuickSort(arr,low,pivot-1);
        _QuickSort(arr,pivot+1,high);
        }
    }
    void quick(std::vector<int>& arr,int left,int right){
        if(left>=right){
            return;
        }
        int key=arr[rand()%(right-left+1)+left];
        int l=left-1,r=right+1,i=left;
        while(i<r){
            if(arr[i]<key) std::swap(arr[++l],arr[i++]);
            else if(arr[i]==key) ++i;
            else std::swap(arr[--r],arr[i]);
        }
        quick(arr,left,l);
        quick(arr,r,right);
    }
    void QuickSort(std::vector<int>& arr){
        int n=arr.size();
        srand(time(nullptr));
        quick(arr,0,n-1);
    }

    //堆排序
        //原理：利用堆（一个近似完全二叉树）的结构，同时满足子节点的键值或索引总是小于（大于）它的父节点
        //时间复杂度：O(N*logN)
    void adjustHeap(std::vector<int>& arr,int left,int right){
        int dad=left;
        for(int i=2*left+1;i<=right;i=2*i+1){
            if(i<right && arr[i]<arr[i+1]){
                ++i;
            }
            if(arr[i]>arr[dad]){
                std::swap(arr[dad],arr[i]);
                dad=i;
            }else{
                return;
            }
        }
    }
    void HeapSort(std::vector<int>& arr){
        int len=arr.size();
        for(int i=(len/2)-1;i>=0;--i){
            adjustHeap(arr,i,len-1);
        }
        for(int i=len-1;i>0;--i){
            std::swap(arr[0],arr[i]);
            adjustHeap(arr,0,i-1);
        }
    }

    //
}


#endif
